#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

struct SkiplistNode
{
    SkiplistNode(int val, size_t level)
        :_val(val)
        , _nextV(level, nullptr)
    {}

    int _val;
    vector<SkiplistNode*> _nextV;
};

class Skiplist {
    typedef SkiplistNode Node;
public:
    Skiplist()
    {
        srand(time(0));
        _head = new SkiplistNode(-1, 1);
    }

    bool search(int target) {
        Node* cur = _head;
        int level = _head->_nextV.size() - 1;

        while (level >= 0)
        {
            if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
            {
                cur = cur->_nextV[level];
            }
            else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target)
            {
                level--;
            }
            else
            {
                return true;
            }
        }

        return false;
    }

    vector<Node*> FindPrevNode(int num)
    {
        int level = _head->_nextV.size() - 1;
        Node* cur = _head;
        vector<Node*> prev(level + 1, _head);

        while (level >= 0)
        {
            if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
            {
                cur = cur->_nextV[level];
            }
            else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num)
            {
                prev[level] = cur;
                level--;
            }
        }

        return prev;
    }

    void add(int num) {
        vector<Node*> prev = FindPrevNode(num);

        size_t newlevel = Random();
        Node* newnode = new Node(num, newlevel);

        if (newlevel > _head->_nextV.size())
        {
            _head->_nextV.resize(newlevel, nullptr);
            prev.resize(newlevel, _head);
        }

        for (size_t i = 0; i < newlevel; ++i)
        {
            newnode->_nextV[i] = prev[i]->_nextV[i];

            prev[i]->_nextV[i] = newnode;
        }
    }

    bool erase(int num) {
        vector<Node*> prev = FindPrevNode(num);
        if (prev[0]->_nextV[0] == nullptr || prev[0]->_nextV[0]->_val != num)
            return false;

        Node* del = prev[0]->_nextV[0];
        for (size_t i = 0; i < del->_nextV.size(); ++i)
        {
            prev[i]->_nextV[i] = del->_nextV[i];
        }
        delete del;


        return true;
    }

    size_t Random()
    {
        size_t level = 1;
        while (rand() <= RAND_MAX * _p && level < _maxlevel)
        {
            ++level;
        }
        return level;
    }

private:
    Node* _head;
    size_t _maxlevel = 32;
    double _p = 0.25;
};

int main()
{


	return 0;
}